|
|
CS 116 Tutorial 4 (Solutions): Lists, Mutation
Reminders:
- Assignment 04 is due on Wed, Oct 9th at 10am
Questions 1, 2, and 3 use the following data definition:
A Card is a list of length 2 where
- the first item is an integer between 1 and 13, inclusive, representing the value of the card, and
- the second item is a string ("hearts", "spades", "clubs", or "diamonds") representing the suit of the card.
Example: [1, "hearts"] represents the ace of hearts
-
Write a function create_cards that consumes a list of card values (integers between 1 and 13),
and a list of suite values (one of the four suit strings),
and returns a list of cards created pair-wise from the consumed lists (values and suits).
Example: create_cards([4,1,10], ["hearts","diamonds","clubs"]) => [ [4,"hearts"], [1, "diamonds"], [10, "clubs"] ].
Solution:
import check
def create_cards(values, suits):
'''returns a sorted list of cards with indicated values and suits.
The produced list has the same length as values and suits.
create_cards: (listof Nat)
(listof (anyof "hearts" "spades" "clubs" "diamonds"))
-> (listof Card)
Requires: len(values) == len(suits)
1 <= all elements of values <= 13
Examples:
create_cards([],[]) => []
create_cards([4,1,10], ['hearts', 'diamonds', 'clubs'])
=> [[1, 'diamonds'],[4,'hearts'], [10, 'clubs'] ]
'''
if values == []:
return []
else:
return [ [values[0], suits[0]] ] + create_cards(values[1:], suits[1:])
## An alternative solution using map with 2 parameters
def create_cards(values,suits):
return list(map(lambda x, y:[x,y],values,suits))
check.expect("cc1", create_cards([],[]), [])
check.expect("cc2", create_cards([4], ['hearts']), [ [4,'hearts'] ])
L = ['hearts', 'spades', 'spades', 'diamonds', 'clubs', 'hearts']
check.expect("cc3", create_cards([6,2,5,4,3,1], L),
[ [6, 'hearts'], [2,'spades'], [5,'spades'], [4, 'diamonds'], [3,'clubs'], [1,'hearts']])
-
Write a function choose_by_colour that consumes a list of cards (hand) and a
string "red" or "black" (colour) and returns a list of the values of the cards in hand of
the appropriate colour (spades and clubs are "black", hearts and diamonds are "red").
Example: choose_by_colour([[1,'hearts'], [9, 'spades'], [3,'diamonds']], 'red') => [1,3].
Solution:
import check
def choose_by_colour(hand, colour):
'''
returns the list of values of the cards in hand which are of the specified
colour ('red' or 'black')
choose_bv_colour: (listof Card) (anyof 'red' 'black') -> (listof Nat)
Examples:
choose_by_colour([], 'red') => []
choose_by_colour([[1,'hearts'], [9, 'spades'], [3,'diamonds']], 'red') => [1,3]
'''
if hand == []:
return []
if colour == 'red' and (hand[0][1]=='diamonds' or hand[0][1]=='hearts'):
return [hand[0][0]] + choose_by_colour(hand[1:], colour)
elif colour == 'black' and (hand[0][1]=='spades' or hand[0][1]=='clubs'):
return [hand[0][0]] + choose_by_colour(hand[1:], colour)
else:
return choose_by_colour(hand[1:], colour)
# Constants for testing
hearts3 = [3, 'hearts']
clubs2 = [2, 'clubs']
diamonds4 = [4, 'diamonds']
spades9 = [9, 'spades']
check.expect("cbc-t1", choose_by_colour([], 'red'), [])
check.expect("cbc-t2", choose_by_colour([hearts3], 'red'), [3])
check.expect("cbc-t3", choose_by_colour([clubs2], 'red'), [])
check.expect("cbc-t4", choose_by_colour([diamonds4], 'red'), [4])
check.expect("cbc-t5", choose_by_colour([spades9], 'red'), [])
check.expect("cbc-t6", choose_by_colour([hearts3], 'black'), [])
check.expect("cbc-t7", choose_by_colour([clubs2], 'black'), [2])
check.expect("cbc-t8", choose_by_colour([diamonds4], 'black'), [])
check.expect("cbc-t9", choose_by_colour([spades9], 'black'), [9])
check.expect("cbc-t10", choose_by_colour([hearts3, clubs2, diamonds4, spades9], 'red'), [3,4])
check.expect("cbc-t11", choose_by_colour([hearts3, clubs2, diamonds4, spades9], 'black'), [2,9])
-
a) Write a function flip_colour that takes in a card, c, and mutates the
suit of that card to a different colour: if c is a heart, it is mutated to a spade (and vice versa),
while if c is a club, it is mutated to a diamond
(and vice versa).
b) Write a function flip_hand that reads in a list of cards (hand),
and mutates the suit of each card in the list so that their colours are flipped in the same way as in
flip_colour.
Solution:
a)
# example definitions:
diamond4 = [4,"diamonds"]
heart3 = [3,'hearts']
import check
def flip_colour (c):
'''
mutates the suit of c: hearts becomes spades (and vice versa) and clubs
becomes diamonds (and vice versa)
Effects: the suit field of c is mutated
flip_colour: Card -> None
Examples:
if flip_colour (diamond4) is called then diamond4 will equal [4,'clubs']
if flip_colour (heart3) is called then heart3 will equal [3,'spades']
'''
# Note that we cannot save c[1] as a local variable because it will
# not alias the way we need; draw a memory diagram if this is unclear
if c[1] == 'hearts':
c[1] = 'spades'
elif c[1] == 'spades':
c[1] = 'hearts'
elif c[1] == 'clubs':
c[1] = 'diamonds'
elif c[1] == 'diamonds':
c[1] = 'clubs'
# Tests:
club4 = [4,"clubs"]
check.expect("flip_colour Test 1 (function)", flip_colour(club4), None)
check.expect("flip_colour Test 1 (card)", club4, [4,'diamonds'])
diamond4 = [4,"diamonds"]
check.expect("flip_colour Test 2 (function)", flip_colour(diamond4), None)
check.expect("flip_colour Test 2 (card)", diamond4, [4,'clubs'])
spade3 = [3,'spades']
check.expect("flip_colour Test 3 (function)", flip_colour(spade3), None)
check.expect("flip_colour Test 3 (card)", spade3, [3,'hearts'])
heart3 = [3, 'hearts']
check.expect("flip_colour Test 4", flip_colour (heart3), None)
check.expect("flip_colour Test 4", heart3, [3,'spades'])
b)
import check
def flip_hand_from(hand, position):
'''
Mutates the suits of all cards in hand from position to the end of the list
Effects: Mutates the suit fields of all cards in hand[position:]
flip_hand_from: (listof Card) Nat -> None
'''
if position < len(hand):
flip_colour(hand[position])
flip_hand_from(hand, position+1)
def flip_hand(hand):
'''
mutates the suit of each card in hand: hearts becomes spades
(and vice versa) and clubs becomes diamonds (and vice versa)
Effects: Mutates the suit field of each card in the list
flip_hand_alt: (listof Card) -> None
Examples:
if lst = [] and flip_hand_alt(lst) is called, lst becomes []
if lst = [[5, 'hearts'], [1, 'diamonds']] and flip_hand_alt(lst) is called,
lst becomes [[5, 'spades], [1, 'clubs']]
'''
flip_hand_from(hand, 0)
# Tests:
lst = []
check.expect("flip_hand Test 1 (function)", flip_hand(lst), None)
check.expect("flip_hand Test 1 (list)", lst, [])
lst = [[7, 'spades']]
check.expect("flip_hand Test 2 (function)", flip_hand(lst), None)
check.expect("flip_hand Test 2 (list)", lst, [[7, 'hearts']])
lst = [[6,'clubs'], [9,'hearts'], [2,'diamonds']]
check.expect("flip_hand Test 3 (function)", flip_hand(lst), None)
check.expect("flip_hand Test 3 (list)",
lst,
[[6,'diamonds'], [9,'spades'], [2,'clubs']])
-
Write a function modify_list that consumes a list of integers (nums)
and a single integer (n). The function returns None, but mutates the list in the following way:
- If
n does not appear in nums then add it to the end of nums.
- If
n appears once, then remove n from nums
- If
n appears at least twice, remove the first and last occurrences of n.
For example:
If L = [], modify_list(L,10) => None, and L = [10]
If L = [1,2,3], modify_list(L,10) => None, and L = [1,2,3,10]
If L = [1,2,3,4], modify_list(L,4) => None, and L = [1,2,3]
If L = [1,5,2,1,7,1,9], modify_list(L,1) => None, and L = [0,5,2,1,7,0,9]
Solution:
import check
def index_of_last(vals, n, position):
'''
returns the index of the last occurrence of n in vals[:position+1], where
0 <= position < len(vals)-1, and n occurs at least once in this range.
index_of_last: (listof Int) Int Int -> Int
Requires: position >= 0
'''
if vals[position]==n:
return position
else:
return index_of_last(vals, n, position-1)
def modify_list(nums, n):
'''
mutates nums to reflect the following conditions:
If n does not appear in nums, it is added to the end of it. If n appears exactly
once in the list, then remove it from nums. If n appears two of more times in nums,
the first and last occurrences of n is removed.
Effects: nums is mutuated
modify_list: (listof Int) Int -> None
Examples:
* if L = [], modify_list(L,10) => None, and L = [10]
* if L = [1,2,3], modify_list(L,10) => None, and L = [1,2,3,10]
* if L = [1,2,3,4], modify_list(L,4) => None, and L = [1, 2, 3]
* if L = [1,5,2,1,7,1,9], modify_list(L,1) => None, and L = [5,2,1,7,9]
Be sure to use list methods as part of your solution (though you can use recursion in
a helper function if needed).
'''
num_times = nums.count(n)
if num_times==0:
nums.append(n)
elif num_times==1:
nums.remove(n)
else:
first_place = nums.index(n)
nums.pop(first_place)
last_place = index_of_last(nums, n, len(nums)-1)
nums.pop(last_place)
# Tests:
L = []
check.expect("ml-1", modify_list(L, 3), None)
check.expect("m1-1(L)", L, [3])
check.expect("ml-2", modify_list(L,3), None)
check.expect("ml-2(L)", L, [])
L = [4,4]
check.expect("ml-3", modify_list(L,4), None)
check.expect("ml-3(L)", L, [])
L = [-1,-1,-1]
check.expect("ml-4", modify_list(L,-1), None)
check.expect("ml-4(L)", L, [-1])
L = [2,4,3,2,5,7,6,2,5,7]
check.expect("ml-5", modify_list(L,2), None)
check.expect("ml-5(L)", L, [4,3,2,5,7,6,5,7])
check.expect("ml-6", modify_list(L,7), None)
check.expect("ml-6(L)", L, [4,3,2,5,6,5])
check.expect("ml-7", modify_list(L,0), None)
check.expect("ml-7(L)", L, [4,3,2,5,6,5,0])
-
Write a function sanitize that consumes a string, s, and returns a
similar string but with any non-alphanumeric characters removed.
For example: sanitize("@Test@") => "Test"
Solution:
import check
def sanitize(s):
'''
returns a string like s, but with all non-alphanumeric characters removed from it.
sanitize: Str -> Str
Examples:
sanitize("") => ""
sanitize("Test") => "Test"
sanitize("@Test@") => "Test"
sanitize("!!@#$!") => ""
'''
return ''.join(list(filter(lambda x: x.isalpha(),s)))
# Tests:
check.expect("sanitize1", sanitize(""), "")
check.expect("sanitize2", sanitize("Test"), "Test")
check.expect("sanitize3", sanitize("Test!"), "Test")
check.expect("sanitize4", sanitize("Hello World"), "HelloWorld")
check.expect("sanitize5", sanitize("!@#$@TEST()()()123!@#!4"), "TEST1234")
check.expect("sanitize6", sanitize("!@#$%^($)*@"), "")
-
Write a function reversed_list a list of string, L, and returns a
list containing the elements of L in reverse order. Write this function using
abstract list functions.
For example: reversed_list(["I","love","cs116"]) => ['cs116','love',I]
Solution:
import check
def reversed_list(L):
'''returns a list by reversing all elements in L.
reversed_list: (listof Str) -> (listof Str)
Examples:
reversed_list([""]) => [""]
reversed_list(["y"]) => ["y"]
reversed_list(['I','love','cs116']) => ['cs116','love',I]
'''
return list(map(lambda i: L[-i], range(1,len(L)+1)))
# Examples:
check.expect("reversed_list_empty", reversed_list([""]), [""])
check.expect("reversed_list single item", reversed_list(["y"]), ["y"])
check.expect("reversed_list_short", reversed_list(['I','love','cs116']), ['cs116','love','I'])
# Tests:
check.expect("reversed_list_single item", rotate(["hahahaha"]), ["hahahaha"])
check.expect("reversed_list_single_item_empty_str", rotate([""]), [""])
check.expect("reversed_list_short", rotate(['1','2','3']), ['3','2','1'])
check.expect("reversed_list_long",
rotate(['I','love','cs116','do','you','yes','you','do']),
['do', 'you', 'yes', 'you', 'do', 'cs116', 'love', 'I'])
|